package lbj.cyw.dp;


/*
* 337.打家劫舍3.  树形动态规划
*   考虑最后一步时,要先考虑遍历方式 ,一般为后序遍历, 最后一步为所有的叶子结点,
*   因为是递归看也看作是同时发生的,左右子节点 互不影响,跟数组不一样要分开考虑
*
* */
public class Rob337 {
    public int rob(TreeNode root) {
        if(root==null){
            return 0;
        }
        int[] res=dfs(root);
        return Math.max(res[0],res[1]);
    }

    private int[] dfs(TreeNode root) {
        if(root==null){
            return new int[]{0,0};
        }
        int[] left=dfs(root.left);
        int[] right=dfs(root.right);
        int[] tmp=new int[2];
        tmp[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        tmp[1]=left[0]+right[0]+root.val;
        return tmp;
    }
}
